import functools
class Solution(object):
    def numPermsDISequence(self, s):
        n = len(s)
        base = 10 ** 9 + 7
        @functools.cache
        def dfs(i, k):
            if i == 0:
                return 1
            else:
                now_item = 0
                if s[i - 1] == 'I':
                    for j in range(k):
                        now_item = (now_item + dfs(i - 1, j)) % base
                else:
                    for j in range(k, i):
                        now_item = (now_item + dfs(i - 1, j)) % base
                return now_item
        ans = 0
        for i in range(n + 1):
            ans = (ans + dfs(n, i)) % base
        return ans

data = Solution()
s = "DID"
print(data.numPermsDISequence(s))
